/*
 * Arbol.cpp
 *
 *  Created on: 01/11/2009
 *      Author: julfc
 */

#include "Arbol.h"

Arbol::Arbol() {
	this->NODO_RAIZ = 1;
	this->NODO_HOJA = 2;
	this->NODO_INDICE = 3;
	this->COMIENZO_RAIZ	= 12;
	this->CANT_CLAVES_INDICE_MAX = 5;
	this->CANT_PUNTEROS_MAX	= 6;
	this->CANT_REGISTROS_MAX = 7;
	this->LONG_REGISTROS = 8;
	this->LONG_PUNTERO = 8;
	this->HIJO_IZQ = 0;
	this->HIJO_DER = 1;
	this->LONG_CLAVE = 20;
	this->TAM_NODO_HOJA = 18 + (this->CANT_REGISTROS_MAX * this->LONG_CLAVE) + (this->CANT_REGISTROS_MAX * this->LONG_REGISTROS);
	this->TAM_NODO_INDICE = 18 + (this->CANT_CLAVES_INDICE_MAX * this->LONG_CLAVE) + (this->CANT_PUNTEROS_MAX * this->LONG_PUNTERO);
	this->TAM_NODO_RAIZ	=  18 + (this->CANT_REGISTROS_MAX * this->LONG_CLAVE) + (this->CANT_PUNTEROS_MAX * this->LONG_PUNTERO) + (this->CANT_REGISTROS_MAX * this->LONG_REGISTROS);
}

void Arbol::Crear(char* filePathName) throw (exception) {
	try	{
		this->file = new fstream (filePathName, ios::in | ios::out | ios::trunc | ios::binary);

		this->CantNodosHojas = 0;
		this->CantNodosIndice = 0;
		this->UltimoBloque = 0;

		//Guardo los datos de control del arbol
		this->file->seekp(0, ios::beg);

		this->file->write((char*)(&(this->CantNodosIndice)), sizeof(int));
		this->file->write((char*)(&(this->CantNodosHojas)), sizeof(int));
		this->file->write((char*)(&(this->UltimoBloque)), sizeof(int));

		this->raiz = Nodo(NODO_RAIZ);

		this->raiz.Save(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
		this->file->flush();
	} catch(exception e) {
		throw e;
	}
}

void Arbol::Abrir(char* filePathName) throw (exception) {
	try	{
		//Leo los datos de control del arbol
		this->file = new fstream (filePathName, ios::in | ios::out | ios::trunc | ios::binary);
		this->file->seekg(0, ios::beg);
		//TODO Ver porque los lee en otro órden.
		this->file->read((char*)(this->CantNodosIndice), sizeof(this->CantNodosIndice));
		this->file->read(reinterpret_cast<char*>(&(this->CantNodosHojas)), sizeof(this->CantNodosHojas));
		this->file->read(reinterpret_cast<char*>(&(this->UltimoBloque)), sizeof(this->UltimoBloque));
		Nodo nodo = this->raiz.Obtener(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
		this->raiz = nodo;
	} catch (exception e) {
		throw e;
	}
}

void Arbol::Cerrar() throw (exception) {
	try	{
		this->file->close();
	} catch(exception e) {
		throw e;
	}
}

void Arbol::InsertarRegistro(string* clave, RegistroArbol* registro) throw (exception) {
	try	{
		string* claveCompleta = this->CompletarClave(clave);
		//Verifico si la raiz esta siendo usada como hoja o no
		if(this->raiz.punteros->empty()) {
			//Verifico que no este llena
			if(this->raiz.cantRegistrosUsados < CANT_REGISTROS_MAX) {
				this->AgregarClaveOrdenada(&(this->raiz), claveCompleta, registro);
				this->raiz.cantClavesUsadas++;
				this->raiz.cantRegistrosUsados++;
				this->raiz.Save(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
			} else {
				//Agrego la clave igual y despues hago el split
				this->AgregarClaveOrdenada(&(this->raiz), claveCompleta, registro);
				Nodo* hijoIzq = this->CrearHijo(&(this->raiz), HIJO_IZQ);

				Referencia* puntIzq = new Referencia();

				puntIzq->bloque = hijoIzq->numBloque;
				puntIzq->offset = this->ObtenerProximoBloqueLibre();


				this->CantNodosHojas++;
				this->UltimoBloque++;

				Nodo* hijoDer = this->CrearHijo(&(this->raiz), HIJO_DER);

				Referencia* puntDer = new Referencia();
				puntDer->bloque = hijoDer->numBloque;
				puntDer->offset = this->ObtenerProximoBloqueLibre();

				hijoIzq->siguiente = puntDer->offset;

				hijoDer->Save(this->file, puntDer->offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
				hijoIzq->Save(this->file, puntIzq->offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
				this->CantNodosHojas++;
				this->UltimoBloque++;

				//Rearmo la raiz
				this->raiz.claves->clear();
				this->raiz.punteros->clear();
				this->raiz.registros->clear();
				this->raiz.cantClavesUsadas = 1;
				this->raiz.cantRegistrosUsados = 0;

				this->raiz.claves->push_back(hijoIzq->claves->back());

				this->raiz.punteros->push_back(*puntIzq);
				this->raiz.punteros->push_back(*puntDer);

				this->raiz.Save(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, NODO_INDICE);

				// Guardo los datos de control del arbol
				this->file->seekp(0, ios::beg);
				this->file->write((char*)(&(this->CantNodosIndice)), sizeof(int));
				this->file->write((char*)(&(this->CantNodosHojas)), sizeof(int));
				this->file->write((char*)(&(this->UltimoBloque)), sizeof(int));
			}
		} else {
			//Se busca el nodo donde debe ir y se inserta
			list<Referencia> camino;
			Referencia puntero;
			puntero.offset = COMIENZO_RAIZ;
			puntero.bloque = this->raiz.numBloque;
			camino.push_back(puntero);

			int offset = this->BuscarSiguiente(&(this->raiz), claveCompleta);
			Nodo nodo;
			nodo = nodo.Obtener(this->file, offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);

			while(nodo.tipo != NODO_HOJA) {
				Referencia puntAux;
				puntAux.offset = offset;
				puntAux.bloque = nodo.numBloque;
				camino.push_back(puntAux);
				offset = this->BuscarSiguiente(&nodo, claveCompleta);
				nodo = nodo.Obtener(this->file, offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
			}
			//Agrego la clave y luego checkeo si hay que hacer split o no
			this->AgregarClaveOrdenada(&nodo, claveCompleta, registro);

			if(nodo.cantRegistrosUsados < CANT_REGISTROS_MAX) {
				nodo.cantClavesUsadas++;
				nodo.cantRegistrosUsados++;
				nodo.Save(this->file, offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
			} else {
				//	SPLIT!!
				nodo.cantClavesUsadas++;
				nodo.cantRegistrosUsados++;
				//Hago Split de la hoja (la izquierda queda en el mismo bloque, se crea su hermano derecho)
				Nodo nodoDer;
				nodoDer.tipo = NODO_HOJA;
				int cantRegistros = (CANT_REGISTROS_MAX + 1) / 2;
				this->UltimoBloque++;
				nodoDer.numBloque = this->UltimoBloque;

				list<string>::iterator itClavAux;
				list<RegistroArbol>::iterator itRegAux;
				for(int j = cantRegistros; j <= CANT_REGISTROS_MAX; j++) {
					int pos = CANT_REGISTROS_MAX + 1 - cantRegistros;
					itRegAux = nodo.registros->begin();
					advance(itRegAux, pos);
					RegistroArbol regAux = *itRegAux;
					nodoDer.registros->push_back(regAux);
					nodo.registros->erase(itRegAux);

					itClavAux = nodo.claves->begin();
					advance(itClavAux, pos);
					string claveSaca = *itClavAux;
					nodoDer.claves->push_back(claveSaca);
					nodo.claves->erase(itClavAux);

					nodoDer.cantClavesUsadas++;
					nodoDer.cantRegistrosUsados++;
					nodo.cantClavesUsadas--;
					nodo.cantRegistrosUsados--;
				}

				int offsetDer = this->ObtenerProximoBloqueLibre();
				this->CantNodosHojas++;

				Referencia* punteroHijoNuevo = new Referencia();
				punteroHijoNuevo->offset = offsetDer;
				punteroHijoNuevo->bloque = nodoDer.numBloque;

				nodoDer.siguiente = nodo.siguiente;
				nodo.siguiente = offsetDer;

				nodoDer.Save(this->file, offsetDer, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
				nodo.Save(this->file, offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);

				string* claveAPromover = &(nodo.claves->back());
				this->Promover(&camino, punteroHijoNuevo, claveAPromover);
				// Guardo los datos de control del arbol
				this->file->seekp(0, ios::beg);
				this->file->write((char*)(&(this->CantNodosIndice)), sizeof(int));
				this->file->write((char*)(&(this->CantNodosHojas)), sizeof(int));
				this->file->write((char*)(&(this->UltimoBloque)), sizeof(int));
			}
		}
		this->file->flush();
	} catch(exception e) {
		throw e;
	}
}

bool Arbol::Eliminar(string* clave) throw (exception) {
	try	{
		string* claveFormateada = this->CompletarClave(clave);
		//Si la raiz no tiene punteros es porque se usa como hoja tambien y la busco ahi directo y si esta lo borro
		if(this->raiz.punteros->empty()) {
			//Busco la posicion de la clave para saber la posicion del registro
			list<RegistroArbol>::iterator itRegistros = this->raiz.registros->begin();
			list<string>::iterator itClaves = this->raiz.claves->begin();
			for(int i = 0; i < this->raiz.cantClavesUsadas; i++)	{
				if(itClaves->compare(*claveFormateada) == 0) {
					this->raiz.claves->erase(itClaves);
					this->raiz.registros->erase(itRegistros);
					this->raiz.cantClavesUsadas--;
					this->raiz.cantRegistrosUsados--;
					this->raiz.Save(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
					return true;
				}
				itClaves++;
				itRegistros++;
			}
		} else {
			Referencia proximo;
			RegistroArbol registro;
			Nodo nodo;
			bool encontrado = BuscarInterno(&(this->raiz), claveFormateada, &(proximo), &(registro));
			bool busquedaExitosa = false;
			nodo = nodo.Obtener(this->file, proximo.offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
			while (!encontrado)	{
				busquedaExitosa = BuscarInterno(&nodo, claveFormateada, &(proximo), &(registro));
				if(busquedaExitosa) {
					list<RegistroArbol>::iterator itRegistros = this->raiz.registros->begin();
					list<string>::iterator itClaves = this->raiz.claves->begin();
					for(int i = 0; i < this->raiz.cantClavesUsadas; i++)	{
						if(itClaves->compare(*claveFormateada) == 0) {
							nodo.claves->erase(itClaves);
							nodo.registros->erase(itRegistros);
							nodo.cantClavesUsadas--;
							nodo.cantRegistrosUsados--;
							nodo.Save(this->file, proximo.offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
							return true;
						}
						itClaves++;
						itRegistros++;
					}
					return true;
				}
				else {
					if(proximo.bloque == -1 && proximo.offset == -1)
						return false;
					else {
						nodo.Limpiar();
						nodo = nodo.Obtener(this->file, proximo.offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
					}
				}
			}
		}
		return false;
	} catch(exception e) {
		throw e;
	}
}

RegistroArbol* Arbol::ObtenerRegistro(string* clave) throw (exception) {
	string* claveFormateada = this->CompletarClave(clave);

	//Si la raiz no tiene punteros es porque se usa como hoja tambien y la busco ahi directo
	if(this->raiz.punteros->size() == 0) {
		//Busco la posicion de la clave para saber la posicion del registro
		list<RegistroArbol>::iterator itRegistros = this->raiz.registros->begin();
		list<string>::iterator itClaves = this->raiz.claves->begin();
		for(int i = 0; i < this->raiz.cantClavesUsadas; i++)	{
			if(itClaves->compare(*claveFormateada) == 0)
				return (&(*itRegistros));
			itClaves++;
			itRegistros++;
		}
	} else {
		//La raiz no es hoja
		Referencia* proximo = new Referencia();
		RegistroArbol* registro = new RegistroArbol();
		Nodo nodo;

		bool encontrado = BuscarInterno(&(this->raiz), claveFormateada, proximo, registro);
		bool busquedaExitosa = false;

		if(encontrado)
			return registro;
		else {
			nodo = nodo.Obtener(this->file, proximo->offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
			while (!encontrado)	{
				busquedaExitosa = BuscarInterno(&nodo, claveFormateada, proximo, registro);
				if(busquedaExitosa)
					return registro;
				else {
					if(proximo->bloque == -1 && proximo->offset == -1)
						return NULL;
					else {
						nodo.Limpiar();
						nodo = nodo.Obtener(this->file, proximo->offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
					}
				}
			}
		}
	}
	return NULL;
}

int Arbol::ObtenerProximoBloqueLibre() {
	//Haciendo la cuenta con los tamaños de los nodos y la cantidad, obtengo el proximo bloque a escribir
	return ((this->CantNodosHojas * TAM_NODO_HOJA) + (this->CantNodosIndice * TAM_NODO_INDICE) + (TAM_NODO_RAIZ) + 12 /*Header arbol*/);
}

void Arbol::AgregarClaveOrdenada(Nodo* nodo, string* clave, RegistroArbol* registro) {
	if(nodo->claves->empty()) {
		nodo->claves->push_back(*clave);
		nodo->registros->push_back(*registro);
	} else {
		//Busco la posicion
		unsigned int k = 0;
		list<string>::iterator itClaves = nodo->claves->begin();
		while (itClaves != nodo->claves->end() && itClaves->compare(*clave) < 0) {
			itClaves++;
			k++;
		}
		//Si hay que agregarla al final
		if(k >= nodo->claves->size()) {
			nodo->claves->push_back(*clave);
			nodo->registros->push_back(*registro);
		} else {
			list<string>::iterator itClaves = nodo->claves->begin();
			list<RegistroArbol>::iterator itRegistros = nodo->registros->begin();
			for (unsigned int i = 0; i < k; i++) {
				itClaves++;
				itRegistros++;
			}
			nodo->claves->insert(itClaves, *clave);
			nodo->registros->insert(itRegistros, *registro);
		}
	}
}

//Completa la clave de '0' para llevarla a su longitud
string* Arbol::CompletarClave(string* clave) {
	string* stringAux;
	stringAux = new string();
	if(clave->size() < (unsigned int)LONG_CLAVE) {
		stringAux->append(*clave);
		for(int i = clave->length(); i < LONG_CLAVE; i++)
			stringAux->append("0");
	} else {
		stringAux->append(clave->substr(0, LONG_CLAVE));
	}

	//Verifico que no me pase de LONG_CLAVE en bytes, sino achico de atras ya que agregue caracteres demas
	while(sizeof(*stringAux) > (unsigned int)LONG_CLAVE) {
		stringAux->resize(stringAux->length()-1);
	}
	return (stringAux);
}

Nodo* Arbol::CrearHijo(Nodo* padre, char lado) {
	Nodo* nodo = new Nodo(NODO_HOJA);

	int resto = (CANT_REGISTROS_MAX + 1) % 2;
	int cantRegistros = (CANT_REGISTROS_MAX + 1) / 2;
	nodo->numBloque = this->UltimoBloque + 1;

	if(lado == HIJO_IZQ) {
		cantRegistros = cantRegistros + resto; //Sobrecargo el nodo izquierdo
		list<string>::iterator itClaves = padre->claves->begin();
		list<RegistroArbol>::iterator itRegistros = padre->registros->begin();
		for(int i = 0; i < cantRegistros; i++)	{
			this->AgregarClaveOrdenada(nodo, &(*itClaves), &(*itRegistros));
			nodo->cantClavesUsadas++;
			nodo->cantRegistrosUsados++;
			itClaves++;
			itRegistros++;
		}
	} else {
		list<string>::iterator itClaves = padre->claves->begin();
		list<RegistroArbol>::iterator itRegistros = padre->registros->begin();
		advance(itClaves, cantRegistros);
		advance(itRegistros, cantRegistros);
		for(unsigned int i = cantRegistros; i < padre->claves->size(); i++) {
			this->AgregarClaveOrdenada(nodo, &(*itClaves), &(*itRegistros));
			nodo->cantClavesUsadas++;
			nodo->cantRegistrosUsados++;
			itClaves++;
			itRegistros++;
		}
	}
	return nodo;
}

int Arbol::BuscarSiguiente(Nodo* nodo, string* clave) {
	bool termino = false;
	list<string>::iterator itClaves = nodo->claves->begin();
	list<Referencia>::iterator itPuntero = nodo->punteros->begin();
	while(!termino && nodo->claves->end() != itClaves) {
		if(clave->compare(*itClaves) <= 0)
			termino = true;
		else {
			itClaves++;
			itPuntero++;
		}
	}
	//Encontro a donde apuntar
	return ((*itPuntero).offset);
}

void Arbol::Promover(list<Referencia>* camino, Referencia* puntHijoNuevo, string* clave) throw (exception) {
	try	{
		list<Referencia>::iterator itPuntero = camino->begin();
		advance(itPuntero, camino->size()-1);
		Referencia* puntPadre = &(*itPuntero);
		camino->remove(*itPuntero);

		Nodo nodoPadre;
		nodoPadre = nodoPadre.Obtener(this->file, puntPadre->offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
		// Busco lugar para insertar
		unsigned int pos = 0;
		list<string>::iterator itClaves = nodoPadre.claves->begin();
		itPuntero = nodoPadre.punteros->begin();
		while (itClaves != nodoPadre.claves->end() && itClaves->compare(*clave) < 0) {
			itClaves++;
			itPuntero++;
			pos++;
		}
		//Si hay que agregarla al final
		if(pos >= nodoPadre.claves->size()) {
			nodoPadre.claves->push_back(*clave);
			nodoPadre.punteros->push_back(*puntHijoNuevo);
		} else {
			nodoPadre.claves->insert(itClaves, *clave);
			itPuntero++;
			nodoPadre.punteros->insert(itPuntero, *puntHijoNuevo);
		}
		//Verifico si hay que hacer SPLIT o no
		if(nodoPadre.cantClavesUsadas < CANT_CLAVES_INDICE_MAX) {
			nodoPadre.cantClavesUsadas++;
			nodoPadre.Save(this->file, puntPadre->offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
			//Si la raiz fue la ultima modificacion, entonces la cargo de vuelta
			if(nodoPadre.tipo == NODO_RAIZ) {
				this->raiz.Limpiar();
				Nodo raizAux = this->raiz.Obtener(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
				this->raiz = raizAux;
			}
		} else {
			//SPLIT!!
			// Verifico si el split es sobre la raiz o un nodo indice
			if(nodoPadre.tipo == NODO_RAIZ) {
				Nodo* hijoDer = new Nodo(NODO_INDICE);
				Nodo* hijoIzq = new Nodo(NODO_INDICE);

				this->UltimoBloque++;
				hijoDer->numBloque = this->UltimoBloque;
				this->UltimoBloque++;
				hijoIzq->numBloque = this->UltimoBloque;

				int offsetDer = this->ObtenerProximoBloqueLibre();
				this->CantNodosIndice++;
				int offsetIzq = this->ObtenerProximoBloqueLibre();
				this->CantNodosIndice++;

				int resto = (CANT_CLAVES_INDICE_MAX + 1) % 2;
				int cantClaves = (CANT_CLAVES_INDICE_MAX + 1) / 2;

				itClaves = nodoPadre.claves->begin();
				advance(itClaves, cantClaves + resto);
				string* claveArriba = &(*itClaves);
				nodoPadre.claves->remove(*itClaves);

				itClaves = nodoPadre.claves->begin();
				itPuntero = nodoPadre.punteros->begin();
				for(int i = 0; i < cantClaves; i++) {
					hijoIzq->claves->push_back(*itClaves);
					nodoPadre.claves->remove(*itClaves);
					hijoIzq->punteros->push_back(*itPuntero);
					nodoPadre.punteros->remove(*itPuntero);
					hijoIzq->cantClavesUsadas++;
					itClaves = nodoPadre.claves->begin();
					itPuntero = nodoPadre.punteros->begin();
				}
				hijoIzq->punteros->push_back(*itPuntero);

				itClaves = nodoPadre.claves->begin();
				itPuntero = nodoPadre.punteros->begin();
				while(nodoPadre.claves->size() > 0) {
					hijoDer->claves->push_back(*itClaves);
					nodoPadre.claves->remove(*itClaves);
					hijoDer->punteros->push_back(*itPuntero);
					nodoPadre.punteros->remove(*itPuntero);
					itClaves = nodoPadre.claves->begin();
					itPuntero = nodoPadre.punteros->begin();
					hijoDer->cantClavesUsadas++;
				}
				hijoDer->punteros->push_back(*itPuntero);
				nodoPadre.punteros->remove(*itPuntero);

				hijoIzq->Save(this->file, offsetIzq, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
				hijoDer->Save(this->file, offsetDer, NODO_RAIZ, NODO_HOJA, NODO_INDICE);

				//Actualizo la raiz
				this->raiz.cantClavesUsadas = 1;
				this->raiz.cantRegistrosUsados = 0;
				this->raiz.claves->clear();
				this->raiz.punteros->clear();
				this->raiz.registros->clear();

				this->raiz.claves->push_back(*claveArriba);
				Referencia* puntIzq = new Referencia();
				Referencia* puntDer = new Referencia();

				puntIzq->bloque = hijoIzq->numBloque;
				puntDer->bloque = hijoDer->numBloque;
				puntIzq->offset = offsetIzq;
				puntDer->offset = offsetDer;

				this->raiz.punteros->push_back(*puntIzq);
				this->raiz.punteros->push_back(*puntDer);

				this->raiz.Save(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
			} else {
				//Hago Split del nodo indice (el izquierda queda en el mismo bloque, se crea su hermano derecho)
				Nodo* nodoDer = new Nodo(NODO_INDICE);

				this->UltimoBloque++;
				nodoDer->numBloque = this->UltimoBloque;

				int resto = (CANT_CLAVES_INDICE_MAX + 1) % 2;
				int cantClaves = (CANT_CLAVES_INDICE_MAX + 1) / 2;

				itClaves = nodoPadre.claves->begin();
				advance(itClaves, cantClaves + resto);
				string* claveAPromover = &(*itClaves);
				nodoPadre.claves->remove(*itClaves);


				itClaves = nodoPadre.claves->begin();
				itPuntero = nodoPadre.punteros->begin();
				itPuntero++;
				for(int i = 0; i < cantClaves; i++) {
					nodoDer->claves->push_back(*itClaves);
					nodoPadre.claves->remove(*itClaves);
					nodoDer->punteros->push_back(*itPuntero);
					nodoPadre.punteros->remove(*itPuntero);
					nodoDer->cantClavesUsadas++;
					nodoPadre.cantClavesUsadas--;
					itClaves++;
					itPuntero++;
				}
				nodoDer->punteros->push_back(*itPuntero);
				nodoPadre.punteros->remove(*itPuntero);

				int offsetDer = this->ObtenerProximoBloqueLibre();
				this->CantNodosIndice++;

				Referencia* punteroHijoNuevo = new Referencia();
				punteroHijoNuevo->offset = offsetDer;
				punteroHijoNuevo->bloque = nodoDer->numBloque;

				nodoDer->Save(this->file, offsetDer, NODO_RAIZ, NODO_HOJA, NODO_INDICE);
				nodoPadre.Save(this->file, puntPadre->offset, NODO_RAIZ, NODO_HOJA, NODO_INDICE);

				this->Promover(camino, punteroHijoNuevo, claveAPromover);
			}
		}
	}
	catch(exception e) {
		throw e;
	}

}
bool Arbol::BuscarInterno(Nodo* nodo, string* clave, Referencia* puntero, RegistroArbol* registro) {

	bool termino = false;
	list<string>::iterator itClaves = nodo->claves->begin();
	list<RegistroArbol>::iterator itRegistros = nodo->registros->begin();
	list<Referencia>::iterator itPunteros = nodo->punteros->begin();
	while(!termino && itClaves != nodo->claves->end()) {
		if(clave->compare(*itClaves) <= 0)
			termino = true;
		else {
			itClaves++;
			itRegistros++;
			itPunteros++;
		}
	}

	if(termino) {
		//Si es hoja: o lo encontro o no existe en el arbol
		if(nodo->tipo == NODO_HOJA) {
			//Si lo encontro
			if(clave->compare(*itClaves) == 0) {
				registro->bloque = itRegistros->bloque;
				registro->offset = itRegistros->offset;
				//Pseudo-asigno el puntero a null
				puntero->bloque = -1;
				puntero->offset = -1;
				return true;
			} else {
				//Pseudo-asigno el puntero a null
				puntero->bloque = -1;
				puntero->offset = -1;
				//Pseudo-asigno el registro a null
				registro->bloque = -1;
				registro->offset = -1;
				return false;
			}
		} else {
			puntero->bloque = itPunteros->bloque;
			puntero->offset = itPunteros->offset;
			//Pseudo-asigno el registro a null
			registro->bloque = -1;
			registro->offset = -1;
			return false;
		}
	}
	else { //Salio del while porque llego al final
		if(nodo->tipo == NODO_HOJA) {
			//Pseudo-asigno el puntero a null
			puntero->bloque = -1;
			puntero->offset = -1;
			//Pseudo-asigno el registro a null
			registro->bloque = -1;
			registro->offset = -1;
			return false;
		} else {
			puntero->bloque = itPunteros->bloque;
			puntero->offset = itPunteros->offset;
			//Pseudo-asigno el registro a null
			registro->bloque = -1;
			registro->offset = -1;
			return false;
		}
	}
}

void Arbol::Imprimir(int offset) {
	try	{
		Nodo nodo;
		nodo = nodo.Obtener(this->file, offset, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
		cout << "{" << nodo.numBloque << "} ";
		if(nodo.tipo == NODO_HOJA)	{
			for(list<string>::iterator itClaves = nodo.claves->begin(); itClaves != nodo.claves->end(); itClaves++)	{
				cout << "[" << *itClaves << "] ";
			}
			cout << "((" << nodo.siguiente << ")) \n";
		} else if(nodo.tipo == NODO_INDICE)	{
			list<string>::iterator itClaves = nodo.claves->begin();
			list<Referencia>::iterator itPunteros = nodo.punteros->begin();
			for(unsigned int i = 0; i < nodo.claves->size(); i++)	{
				cout << "(" << itPunteros->bloque << ") ";
				cout << "[" << *itClaves << "] ";
				itClaves++;
				itPunteros++;
			}
			cout << "(" << itPunteros->bloque << ") \n";

			for(itPunteros = nodo.punteros->begin(); itPunteros != nodo.punteros->end(); itPunteros++) {
				this->Imprimir(itPunteros->offset);
			}
		} else {
			if(nodo.cantRegistrosUsados > 0) {
				for(list<string>::iterator itClaves = nodo.claves->begin(); itClaves != nodo.claves->end(); itClaves++) {
					cout << "[" << *itClaves << "] ";
				}
				cout << "((" << nodo.siguiente << ")) \n";
			} else {
				list<string>::iterator itClaves = nodo.claves->begin();
				list<Referencia>::iterator itPunteros = nodo.punteros->begin();
				for(unsigned int i = 0; i < nodo.claves->size(); i++)	{
					cout << "(" << itPunteros->bloque << ") ";
					cout << "[" << *itClaves << "] ";
				}
				cout << "(" << itPunteros->bloque << ") \n";

				for(itPunteros = nodo.punteros->begin(); itPunteros != nodo.punteros->end(); itPunteros++) {
					this->Imprimir(itPunteros->offset);
				}
			}
		}
	} catch(exception e) {

	}
}

list<string> Arbol::RecorrerOrdenado() {
	list<string> array;
	Nodo nodo;
	nodo = nodo.Obtener(this->file, COMIENZO_RAIZ, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
	//Verifico si la raiz es nodo hoja
	if(nodo.cantRegistrosUsados > 0) {
		for(list<string>::iterator itClaves = nodo.claves->begin(); itClaves != nodo.claves->end(); itClaves++)	{
			array.push_back(*itClaves);
		}
	} else {
		int offsetProximo = 0;
		list<Referencia>::iterator itPuntero = nodo.punteros->begin();
		while(nodo.tipo != NODO_HOJA)	{
			offsetProximo = itPuntero->offset;
			nodo.Limpiar();
			nodo = nodo.Obtener(this->file, offsetProximo, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
			itPuntero++;
		}
		while(nodo.siguiente != 0) {
			for(list<string>::iterator itClaves = nodo.claves->begin(); itClaves != nodo.claves->end(); itClaves++)	{
				array.push_back(*itClaves);
			}
			offsetProximo = nodo.siguiente;
			nodo.Limpiar();
			nodo = nodo.Obtener(this->file, offsetProximo, NODO_RAIZ, NODO_HOJA, LONG_CLAVE);
		}
		for(list<string>::iterator itClaves = nodo.claves->begin(); itClaves != nodo.claves->end(); itClaves++)	{
			array.push_back(*itClaves);
		}
	}
	return array;
}


Arbol::~Arbol() {
	// TODO Auto-generated destructor stub
}
